﻿using System;
using System.Collections.Generic;

namespace QSharp.Scheme.Utility.HBSpaceMgmt
{
    using Classical.Trees;

    public static class Allotter
    {
        /**
         * <summary>
         *  Parameters:
         *  input -
         *   targetSize     Size of the target space governed by the management system
         *   btreeOrders    Orders of the b-trees in the system from higher rank to lower
         *  output -
         *   sectionSizes   Sizes of the sections in the system. For root section, it is 
         *                  the number of entriess
         * </summary>
         */
        public static void Allot(long targetPageCount, IList<int> btreeOrders,
            out long rootLen, out List<long> btreeSectionLen)
        {
            int c = btreeOrders.Count;

            btreeSectionLen = new List<long>(c);
            for (int i = c - 1; i >= 0; i--)
            {
                int order = btreeOrders[i];
                int minEntryCount = BTree.MinimalEntryCount(order);
                btreeSectionLen[i] = (targetPageCount + minEntryCount - 1) / minEntryCount;
                if (minEntryCount > 2) btreeSectionLen[i]++;
                targetPageCount = btreeSectionLen[i];
            }
            rootLen = (targetPageCount + 1) / 2;
        }

        /**
         * <summary>
         *  Arrange sections for target of specific size 
         *  according to fixed B-tree order, root section size
         * </summary>
         */
        public static void Allot(long targetPageCount, int maxRootLen,
            int btreeOrder, out int rootLen, out List<long> btreeSectionLen)
        {
            long holeCount = (targetPageCount + 1) / 2;
            int minEntryCount = BTree.MinimalEntryCount(btreeOrder);
            btreeSectionLen = new List<long>();

            for (; ; )
            {
                if (holeCount <= maxRootLen)
                {
                    rootLen = (int)holeCount;
                    return;
                }
                else
                {
                    long nodeCount = (holeCount + minEntryCount - 1) / minEntryCount;
                    if (minEntryCount > 2) nodeCount++;
                    btreeSectionLen.Insert(0, nodeCount);
                    holeCount = (nodeCount + 1) / 2;
                }
            }
        }
    }
}
